// Learn TypeScript:
//  - https://docs.cocos.com/creator/manual/en/scripting/typescript.html
// Learn Attribute:
//  - https://docs.cocos.com/creator/manual/en/scripting/reference/attributes.html
// Learn life-cycle callbacks:
//  - https://docs.cocos.com/creator/manual/en/scripting/life-cycle-callbacks.html

/**
 * F = G + H;
 * 
 * 伪算法：
 * 
 * 将起始点加入openlist;
 * while openlist 不为空 then
 *      当前节点 = openlist中F值最小节点;
 *      if 当前节点 = 目标节点 then
 *          路径完成;
 *      else
 *          当前节点移出openlist并移入closelist;
 *          检查当前节点每个相邻节点;
 *          for 相邻节点 then
 *              if 该节点不在openlist and 该节点不在closelist and 该节点不是障碍物 then
 *                  将该节点加入openlist并计算F值;
 */

export class AStarPoint {
    public f: number = 0;
    public g: number = 0;
    public h: number = 0;
    public parent: AStarPoint = null;

    public x: number = 0;
    public y: number = 0;

    public equals(point: AStarPoint): boolean {
        return point.x === this.x && point.y === this.y;
    }
}

export default class AStar {
    //是否允许斜角路径
    public static enableBevel: boolean = false;

    public static debug: boolean = false;

    private _openlist: Array<AStarPoint> = [];
    private _closelist: Array<AStarPoint> = [];

    //标识障碍物的二维表
    private _map: Array<Array<number>> = [];

    private _pointPool: Array<AStarPoint> = [];

    private _startPoint: AStarPoint = null;
    private _endPoint: AStarPoint = null;

    //相邻节点移动代价
    private _coast: number = 1;

    public init(map: Array<Array<number>>) {
        this._map = map;
    }

    public findPath(x1: number, y1: number, x2: number, y2: number): Array<AStarPoint> {
        AStar.debug && console.time("findPath");

        this.clear();

        this._startPoint = this.getPoint(), this._endPoint = this.getPoint();
        this._startPoint.x = x1, this._startPoint.y = y1;
        this._endPoint.x = x2, this._endPoint.y = y2;
        this._openlist.push(this._startPoint);

        let currPoint: AStarPoint = null;
        while (this._openlist.length > 0) {
            currPoint = this.findMinFPoint();
            if (currPoint.equals(this._endPoint)) {
                break;
            } else {
                let index = this._openlist.indexOf(currPoint);
                this._openlist.splice(index, 1);
                this._closelist.push(currPoint);
                //检查当前节点每个相邻节点
                if (AStar.enableBevel) {
                    //左上
                    this.processPoint(currPoint.x - 1, currPoint.y + 1, currPoint);
                    //右上
                    this.processPoint(currPoint.x + 1, currPoint.y + 1, currPoint);
                    //左下
                    this.processPoint(currPoint.x - 1, currPoint.y - 1, currPoint);
                    //右下
                    this.processPoint(currPoint.x + 1, currPoint.y - 1, currPoint);
                }
                //上
                this.processPoint(currPoint.x, currPoint.y + 1, currPoint);
                //下
                this.processPoint(currPoint.x, currPoint.y - 1, currPoint);
                //左
                this.processPoint(currPoint.x - 1, currPoint.y, currPoint);
                //右
                this.processPoint(currPoint.x + 1, currPoint.y, currPoint);
            }
        }

        let path = [];
        if (currPoint) {
            while (currPoint) {
                path.unshift(currPoint);
                currPoint = currPoint.parent;
            }
        }

        AStar.debug && console.timeEnd("findPath");

        return path;
    }

    private processPoint(x: number, y: number, parent: AStarPoint) {
        let xMax = this._map[0] ? this._map[0].length : 0;
        let yMax = this._map.length;
        if (x >= 0 && x < xMax && y >= 0 && y < yMax
            && !this.isPointInList(x, y, this._openlist)
            && !this.isPointInList(x, y, this._closelist)
            && this.isValidPoint(x, y)) {
            let point = this.getPoint();
            point.x = x, point.y = y;
            point.parent = parent;
            point.g = this.gCoast(point);
            point.h = this.hCoast(point);
            point.f = point.g + point.h;
            this._openlist.push(point);
        }
    }

    private findMinFPoint(): AStarPoint {
        let point: AStarPoint = null;
        for (let v of this._openlist) {
            if (!point || point.f > v.f) {
                point = v;
            }
        }
        return point;
    }

    // private fCoast(point: AStarPoint) {
    //     return this.gCoast(point) + this.hCoast(point);
    // }

    private gCoast(point: AStarPoint): number {
        return point.parent.g + this._coast;
    }

    private hCoast(point: AStarPoint): number {
        //曼哈顿距离
        return (Math.abs(point.x - this._endPoint.x) + Math.abs(point.y - this._endPoint.y)) * this._coast;
    }

    private isPointInList(x, y, list: Array<AStarPoint>): boolean {
        let exist: boolean = false;
        for (let v of list) {
            if (v.x === x && v.y === y) {
                exist = true;
                break;
            }
        }
        return exist;
    }

    private isValidPoint(x, y): boolean {
        return this._map[y][x] !== -1;
    }

    public clear() {
        for (let v of this._openlist) {
            this.putPoint(v);
        }

        this._openlist.length = 0;

        for (let v of this._closelist) {
            this.putPoint(v);
        }

        this._closelist.length = 0;

        this._startPoint = null;
        this._endPoint = null;
    }

    private getPoint(): AStarPoint {
        return this._pointPool.length > 0 ? this._pointPool.pop() : new AStarPoint();
    }

    private putPoint(point: AStarPoint) {
        point.x = point.y = -1;
        point.f = point.g = point.h = 0;
        point.parent = null;
        this._pointPool.push(point);
    }
}
